﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace text
{
    /// <summary>
    /// 785.判断二分图
    /// 测试用例
    ///int[][] a = new int[4][];
    ///a[0] = new int[] { 1, 3 };
    ///a[1] = new int[] { 0, 2 };
    ///a[2] = new int[] { 1, 3 };
    ///a[3] = new int[] { 0, 2 };
    ///TuCheck tu = new TuCheck();
    //Console.WriteLine(tu.TraverseTu(a)); 
    /// </summary>
    public class TuCheck
    {
        private int UNCOLORED = 0;
        private int RED = 1;
        private int GREEN = 2;
        private int[] color;
        public bool TraverseTu(int[][] graph)
        {
            int n = graph.Length;//获取顶点的长度
            color = new int[n];
            for (int i = 0; i < n; i++)
            {
                color[i] = UNCOLORED;
            }
            for (int i = 0; i < n; i++)
            {
                if (color[i]==UNCOLORED)
                {
                    Queue<int> queue = new Queue<int>();
                    queue.Enqueue(i);
                    color[i] = RED;
                    while (queue.Count>0)
                    {
                        int node = queue.Dequeue();
                        int cNei = color[node] == RED ? GREEN : RED;
                        for (int j = 0; j < graph[node].Length; j++)
                        {
                            if (color[graph[node][j]]==UNCOLORED)
                            {
                                queue.Enqueue(graph[node][j]);
                                color[graph[node][j]] = cNei;
                            }
                            else if (color[graph[node][j]]!=cNei)
                            {
                                return false;
                            }
                            
                        }              
                    }
                }
            }
            return true ;
        }
    }
}
